//
// Created by Administrator on 2024/4/24.
//

#include "arrUtil.h"
using namespace std;

// 分成小于等于区和大于区 以第一个数为基准
int part(vector<int> &v, int l, int r)
{
    // le是等于区的最右边索引
    int le=l-1;
    int t= v[l];
    for (int i = l; i <=r ; ++i)
    {
        if(v[i]<=t)
        {
            ++le;
            swap(v[i],v[le]);
        }
    }
    swap(v[le],v[l]);
    return le;
}

void quickSort(vector<int> &v,int l,int r)
{
    if (l>=r)
        return;
    int m = part(v,l,r);
    quickSort(v,l,m-1);
    quickSort(v,m+1,r);
}

int main()
{
    vector<int> l{29,10,14,37,15};
//    cout<<part(l,0,l.size()-1)<<endl;
    randVector(l,1000);
    quickSort(l,0,l.size()-1);
//    printVector(l);
    cout<<checkSortVector(l);
    return 0;
}